package cn.xiaolang.function.data_structure;

import cn.xiaolang.function.data_structure.common.SortUtils;

/**
 * 选择排序
 * 1 找出最小数O(n)
 * 2 找出剩余元素的最小值O(n)
 * 时间复杂度：O(n2),不稳定
 *
 * @author Dean
 * @date 2021-08-08
 */
public class SortBySelect {

    public static void main(String[] args) {
        int[] arr = {5, 1, 4, 6, 2, 8, 9, 3, 7};

        for (int j = 0; j < arr.length; j++) {
            int minPos = j;
            int maxPos = arr.length - j - 1;
            if (minPos >= maxPos) {
                break;
            }
            for (int i = j; i <= arr.length - j - 1; i++) {
                if (arr[minPos] > arr[i]) {
                    minPos = i;
                }
                if (arr[maxPos] < arr[i]) {
                    maxPos = i;
                }
            }
            System.out.println("minPos:" + minPos + ",maxPos:" + maxPos);
            SortUtils.swap(arr, j, minPos);
            if (j != maxPos) {
                SortUtils.swap(arr, arr.length - j - 1, maxPos);
            }
            SortUtils.printArr(arr);
        }


    }
}
